package com.insa.flopenshop;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class AlgoGenetique implements Solver {
	private Parametres params;
	private Solution[] chromosomes; 
	
	public AlgoGenetique(Parametres p){
		params = p;
		chromosomes = new Solution[params.getNbChromosomes()];
	}
	
	@Override
	public Solution solve(Instance instance) {
		
		// Initialisation des chromosomes avec des solutions gloutones aléatoires
		if(params.isDebug())
			System.out.println("Intitialisation");
		HeuristiqueGloutonne hg = new HeuristiqueGloutonne(new GetTachePlacableAleatoire(), false);
		for(int i = 0 ; i < params.getNbChromosomes() ; i++){
			chromosomes[i] = hg.solve(instance);
			if(params.isDebug())
				System.out.println("Chromosome " + i + " : " + chromosomes[i]);
		}
		
		
		// Boucle principale, se termine quand le temps de calcul demandé est atteint
		long start_time = System.currentTimeMillis();
		long end_time = 0;
		int i = 0;
		while((end_time - start_time)/1000 < params.getTempsFin()){
			i++;
			if(params.isDebug()){
				System.out.println("============== Generation " + i + " ==============");
				System.out.println("= Mutations ----------------------------");
			}
			mutation();
			if(params.isDebug())
				System.out.println("= Croisements --------------------------");
			croisement();
			if(params.isDebug())
				System.out.println("= Selection ----------------------------");
			selection();
			end_time = System.currentTimeMillis();
		}
		System.out.println("Solution Trouvee en " + i + " generations");

		return getSolutionWithMinTime();
	}

	/*
	 * Effectue des mutations aleatoires sur chaque chromosome
	 */
	private void mutation() {
		for(int i = 0 ; i < params.getNbChromosomes() ; i++){
			if(params.isDebug())
				System.out.println("= - Chromosome " + i);
			// Permutation de deux RU
			if(Math.random() < params.getProbaMutationRU()){
				// Si il y a plus d'une RU
				int nbRU = chromosomes[i].getInstance().getNumRessouceUniversel();
				if(nbRU > 1){
					// On selectionne aleatoirement deux RU
					int idRU1 = (int) Math.floor(Math.random()* (double) nbRU);
					int idRU2 = (int) Math.floor(Math.random()* (double) nbRU);
					if(idRU1 == idRU2)
						idRU2 = (idRU2+1) % nbRU;
					
					// On echange leur position dans le chromosome
					LinkedList<Placement> tmpRU = chromosomes[i].getFileRessourceUniverselle()[idRU1];
					chromosomes[i].getFileRessourceUniverselle()[idRU1] = chromosomes[i].getFileRessourceUniverselle()[idRU2];
					chromosomes[i].getFileRessourceUniverselle()[idRU2] = tmpRU;
					
					// On change la valeur de la RU dan les placemens
					for(Placement p : chromosomes[i].getFileRessourceUniverselle()[idRU1]){
						p.setRessourceUniverselle(idRU1);
					}
					for(Placement p : chromosomes[i].getFileRessourceUniverselle()[idRU2]){
						p.setRessourceUniverselle(idRU2);
					}
					
					if(params.isDebug())
						System.out.println("= -- Permutation RU" + idRU1 + " et RU" + idRU2);
				}
			}
			
			// Permutation de deux T dans une RU
			if(Math.random() < params.getProbaMutationT()){
				int nbRU = chromosomes[i].getInstance().getNumRessouceUniversel();
				// Choisit aléatoirement une RU
				int indexRU = (int) Math.floor(Math.random()* (double) nbRU);
				
				// S'il y a plusieurs taches dans la RU seclectionnee
				LinkedList<Placement> RU = chromosomes[i].getFileRessourceUniverselle()[indexRU];
				int nbTaches = RU.size();
				if(nbTaches > 1){
					// Choisit aleatoirement deux taches dans cette RU
					int idT1 = (int) Math.floor(Math.random()* (double) nbTaches);
					int idT2 = (int) Math.floor(Math.random()* (double) nbTaches);
					if(idT1 == idT2)
						idT2 = (idT2+1) % nbTaches;
					
					// On echange leur position dans la RU
					Placement tmpTache = RU.get(idT1);
					RU.set(idT1, RU.get(idT2));
					RU.set(idT2, tmpTache);
					chromosomes[i].corriger();
					if(params.isDebug())
						System.out.println("= -- Permutation T" + idT1 + " et T" + idT2 + " dans RU" + indexRU);
				}
			}
			
			// Permutation de deux T dans deux RU differentes
			if(Math.random() < params.getProbaMutationTRU()){
				int nbRU = chromosomes[i].getInstance().getNumRessouceUniversel();
				// Si il y a plus d'une RU
				if(nbRU > 1){
					// On selectionne aleatoirement deux RU
					int idRU1 = (int) Math.floor(Math.random()* (double) nbRU);
					int idRU2 = (int) Math.floor(Math.random()* (double) nbRU);
					if(idRU1 == idRU2)
						idRU2 = (idRU2+1) % nbRU;
					
					LinkedList<Placement> RU1 = chromosomes[i].getFileRessourceUniverselle()[idRU1];
					LinkedList<Placement> RU2 = chromosomes[i].getFileRessourceUniverselle()[idRU2];
					int nbTaches1 = RU1.size();
					int nbTaches2 = RU2.size();

					// Choisit aleatoirement deux taches dans chaque RU
					int idT1 = (int) Math.floor(Math.random()* (double) nbTaches1);
					int idT2 = (int) Math.floor(Math.random()* (double) nbTaches2);

					// On echange leur position dans les RU
					Placement tmpTache = RU1.get(idT1);
					RU1.set(idT1, RU2.get(idT2));
					RU2.set(idT2, tmpTache);
					
					chromosomes[i].corriger();
					if(params.isDebug())
						System.out.println("= -- Permutation T" + idT1 + " dans RU" + idRU1 + " et T" + idT2 + " dans RU" + idRU2);
				}
			}
			if(params.isDebug()){
				Verificateur verif = new Verificateur(chromosomes[i]);
				if(!verif.solutionValide())
					System.out.println("= - Erreur : Solution invalide " + chromosomes[i]);
			}
		}
	}
	
	/*
	 * Effectue des croisements aleatoires entre des paires de chromosomes
	 */
	private void croisement() {
		// Reordonne aleatoirement les chromosomes
		ArrayList<Solution> alea = new ArrayList<Solution>(Arrays.asList(chromosomes));
		Collections.shuffle(alea);
		chromosomes = alea.toArray(new Solution[alea.size()]);
		
		// Croise les paires consecutives de chromosomes
		for(int i=0 ; i < chromosomes.length ; i+=2){
			if(params.isDebug())
				System.out.println("= - Chromosomes " + i + " et " + (i+1));
			//S'il y a un nombre impair de chromosomes on ne traite pas le dernier
			if(i+1 < chromosomes.length){
				//Choisit aleatoirement une position pour couper les deux chromosomes (coupe apres l'id tache obtenu)
				int coupe = (int) Math.floor(Math.random()* (double) Math.min(chromosomes[i].getMinSize(), chromosomes[i+1].getMinSize()));
				
				//Memorise l'ordre des taches
				ArrayList<SousTache> ordre1 = chromosomes[i].getOrdreSousTaches();
				ArrayList<SousTache> ordre2 = chromosomes[i+1].getOrdreSousTaches();
				
				//Conserve la solution avant la coupe
				LinkedList<Placement>[] fileRU1 = chromosomes[i].getFileRessourceUniverselle();
				LinkedList<Placement>[] fileRU2 = chromosomes[i+1].getFileRessourceUniverselle();
				boolean fini = false;
				LinkedList<Placement> tmpList = null;
				int j=0;
				while(!fini){
					fini = true;
					if(j < fileRU1.length){
						fini=false;
						tmpList = new LinkedList<Placement>();
						for(int k = 0 ; k <= coupe ; k++){
							tmpList.add(fileRU1[j].get(k));
						}
						fileRU1[j]=tmpList;
					}
					if(j < fileRU2.length){
						fini=false;
						tmpList = new LinkedList<Placement>();
						for(int k = 0 ; k <= coupe ; k++){
							tmpList.add(fileRU2[j].get(k));
						}
						fileRU2[j]=tmpList;
					}
					j++;
				}
				
				//Replace les taches à l'aide de l'heuristique gloutonne dans l'ordre qu'elles avaient dans l'autre chromosome
				chromosomes[i] = (new HeuristiqueGloutonne(new GetTachePlacableSuivantListe(ordre2), params.isDebug())).solve(chromosomes[i].getInstance(), chromosomes[i]);
				chromosomes[i+1] = (new HeuristiqueGloutonne(new GetTachePlacableSuivantListe(ordre1), params.isDebug())).solve(chromosomes[i+1].getInstance(), chromosomes[i+1]);
				if(params.isDebug()){
					Verificateur verif = new Verificateur(chromosomes[i]);
					if(!verif.solutionValide())
						System.out.println("= - Erreur : Solution invalide " + chromosomes[i]);
					verif = new Verificateur(chromosomes[i+1]);
					if(!verif.solutionValide())
						System.out.println("= - Erreur : Solution invalide " + chromosomes[i+1]);
				}
			}
		}
	}
	
	/*
	 * Effectue une selection pour revenir au nombre de chromosomes initial
	 */
	private void selection() {
		int nbChroARetirer = chromosomes.length - params.getNbChromosomes();
		double total, cpt, random;
		
		// On retire des chromosomes jusqu'a retrouver le nombre initial
		for(int j = 0 ; j < nbChroARetirer ; j++){
			// Compte le total des temps
			total = 0;
			for(int i = 0 ; i < chromosomes.length ; i++){
				total += chromosomes[i].getTotalTime();
			}
			
			// Retire aleatoirement un chromosome, plus la solution est longue, plus elle a de chances d'etre retiree
			cpt = 0;
			random = Math.random()*total;
			for(int i = 0 ; i < chromosomes.length ; i++){
				cpt += chromosomes[i].getTotalTime();
				if(random < cpt){
					retirer(i);
					break;
				}
			}
		}
	}
	
	/*
	 * Retire un chromosome de la liste
	 * 
	 * @param : index du chromosome a retirer
	 */
	private void retirer(int index){
		for(int i = index ; i < chromosomes.length - 1 ; i++){
			chromosomes[i]=chromosomes[i+1];
		}
		
		ArrayList<Solution> chro = new ArrayList<Solution>(Arrays.asList(chromosomes));
		chro.remove(chro.size()-1);
		chromosomes = chro.toArray(new Solution[chro.size()]);
		
	}

	/*
	 * Retourne le chromosome avec le temps total le plus faible
	 * 
	 * @return : Meilleure solution
	 */
	private Solution getSolutionWithMinTime(){
		int minTime = chromosomes[0].getTotalTime(), time;
		int minIndex = 0;
		
		for(int i = 0 ; i < params.getNbChromosomes() ; i++){
			time = chromosomes[i].getTotalTime();
			if(time < minTime){
				minIndex = i;
				minTime = time;
			}
		}
		
		return chromosomes[minIndex];
	}

}
